import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Offer22
 * @Description TODO
 * @Author clockTown
 * @Date 2021/8/22 19:55
 * @Version 1.0
 */
class Offer22 {
}

/**
 * v0 两次遍历
 */
class Offer22V0 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode cur = head;
        int l = 0;
        while (cur!= null){
            l ++;
            cur = cur.next;
        }
        l -= k;
        cur = head;
        for (int i = 0; i < l; i++) {
            cur = cur.next;
        }
        return cur;
    }
}

/**
 * v1 使用list存储
 */
class Offer22V1 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode cur = head;
        List<ListNode> list = new ArrayList<>();
        while (cur!= null){
            list.add(cur);
            cur = cur.next;
        }

        return list.get(list.size() - k);
    }
}

/**
 * v2 双指针
 */
class Offer22V2 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        int t = 0;
        while (fast !=null){
            if (t >= k){
                slow = slow.next;
            }
            fast = fast.next;
            t++;
        }
        return slow;
    }
}
